package 递归回溯.二维版;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-06
 **/

public class No212单词搜索II {

    /**
     * 给定一个 m x n 二维字符网格 boardNormal 和一个单词（字符串）列表 words，
     * 找出所有同时在二维网格和字典中出现的单词。
     * 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，
     * 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
     *
     * 示例 1：
     * 输入：boardNormal = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
     * 输出：["eat","oath"]
     * 示例 2：
     * 输入：boardNormal = [["a","b"],["c","d"]], words = ["abcb"]
     * 输出：[]
     *  
     * 提示：
     * m == boardNormal.length
     * n == boardNormal[i].length
     * 1 <= m, n <= 12
     * boardNormal[i][j] 是一个小写英文字母
     * 1 <= words.length <= 3 * 104
     * 1 <= words[i].length <= 10
     * words[i] 由小写英文字母组成
     * words 中的所有字符串互不相同
     */

    /**
     * 利用前缀树来解决问题
     * 1. 将所有单词放入前缀树
     * 2. 对每一个坐标都从前缀树的根开始搜索
     * 3. 搜索也是dfs,截止的标志是下一个坐标对应的字符不是当前前缀树的子节点
     */

    private int[][] around = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private Set<String> result = new HashSet<>();
    private char[][] board;
    private boolean[][] visited;
    private int allLength;
    private int itemLength;

    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        this.allLength = board.length;
        this.itemLength = board[0].length;
        this.visited = new boolean[allLength][itemLength];

        Trie trie = new Trie();
        // 都放入了前缀树
        for (String word : words) {
            trie.insert(word);
        }

        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                visited[i][j] = true;
                dfs(i, j, trie.root.next.get(board[i][j]));
                visited[i][j] = false;
            }
        }

        return new ArrayList<>(result);
    }

    private void dfs(int x, int y, Node cur) {

        if (cur == null) {
            return;
        }
        if (cur.isWord) {
            result.add(cur.value);
        }

        for (int i = 0; i < 4; i++) {
            int nextX = x + around[i][0];
            int nextY = y + around[i][1];
            if (this.valid(nextX, nextY)) {
                char c = board[nextX][nextY];
                Node next = cur.next.get(c);
                visited[nextX][nextY] = true;
                dfs(nextX, nextY, next);
                visited[nextX][nextY] = false;
            }
        }

    }

    private boolean valid(int x, int y) {
        return x >= 0 && x < allLength && y >= 0 && y < itemLength && !visited[x][y];
    }


    static class Trie {

        private Node root = new Node('*', "");

        // 插入操作
        public void insert(String str) {
            char[] arr = str.toCharArray();
            StringBuilder sb = new StringBuilder();
            Node cur = root;
            for (int i = 0; i < arr.length; i++) {
                char c = arr[i];
                sb.append(c);
                cur.next.putIfAbsent(c, new Node(c, sb.toString()));
                cur = cur.next.get(c);
            }
            cur.isWord = true;
        }

    }

    static class Node {

        private char c;
        private Map<Character, Node> next = new HashMap<>();
        private String value;
        private boolean isWord;

        public Node(char c, String value) {
            this.c = c;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        No212单词搜索II n = new No212单词搜索II();
        char[][] arr1 = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
        String[] arr2 = {"oath","pea","eat","rain"};
        List<String> result = n.findWords(arr1, arr2);
        System.out.println(JSON.toJSONString(result));
    }





    private char[][] boardNormal;
    private Set<String> set = new HashSet<>();

    /**
     * 这样不行,搜索了 [words]次 回溯, [words]次可能很多
     * 又二维数组长宽是<=12,所以我们可以求出二维数组所有的单词,并且单词长度<=12的,所以反过来搜索。
     */
    public List<String> findWordsNormal(char[][] board, String[] words) {
        this.boardNormal = board;
        int allLength = board.length;
        int itemLength = board[0].length;

        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                StringBuilder path = new StringBuilder();
                path.append(board[i][j]);
                board[i][j] = '*';
                this.dfs(i, j, path);
                board[i][j] = path.charAt(path.length() - 1);
                path.deleteCharAt(path.length() - 1);
            }
        }

        for (String word : words) {
            if (set.contains(word)) {
                result.add(word);
            }
        }

        return null;
    }

    private void dfs(int x, int y, StringBuilder path){
        if (path.length() > 10) {
            return;
        }
        set.add(path.toString());
        for (int i = 0; i < 4; i++) {
            int nextX = x + around[i][0];
            int nextY = y + around[i][1];
            if (validGo(nextX, nextY)) {
                path.append(boardNormal[nextX][nextY]);
                boardNormal[nextX][nextY] = '*';
                this.dfs(nextX, nextY, path);
                boardNormal[nextX][nextY] = path.charAt(path.length() - 1);
                path.deleteCharAt(path.length() - 1);
            }
        }
    }

    private boolean validGo(int x, int y) {
        return  x >= 0 && x < boardNormal.length && y >= 0 && y < boardNormal[0].length && boardNormal[x][y] != '*';
    }

}
